package com.markus.code.图.图1;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/19 12:57
 * todo: 并查集
 */
public class UnionAndSet {
    public HashMap<Node,Node> fatherMap;
    public HashMap<Node,Integer> sizeMap;
    public UnionAndSet(List<Node> nodes){
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
        for (Node node : nodes) {
            fatherMap.put(node,node);
            sizeMap.put(node,1);
        }
    }
    
    public Node getHeader(Node n1){
        Stack<Node> stack = new Stack<>();
        Node father = fatherMap.get(n1);
        while(n1 != father){
            stack.push(n1);
            n1 = father;
        }
        while(!stack.isEmpty()){
            Node son = stack.pop();
            fatherMap.put(son,father);
        }
        return father;
    }
    
    public void union(Node n1,Node n2){
        //这两个节点需要存在才能进行后续操作
        if (fatherMap.containsKey(n1) && fatherMap.containsKey(n2)){
            Node header_1 = getHeader(n1);
            Node header_2 = getHeader(n2);
            if (header_1 != header_2){
                Node big = header_1;
                Node small = header_2;
                big = sizeMap.get(big)> sizeMap.get(small) ? big : small;
                small = big == header_1 ? small : header_1;
                fatherMap.put(small,big);
                sizeMap.put(big,sizeMap.get(big)+sizeMap.get(small));
            }
        }
    }
    public boolean isSameSet(Node n1,Node n2){
        if (fatherMap.containsKey(n1) && fatherMap.containsKey(n2)){
            Node node1 = fatherMap.get(n1);
            Node node2 = fatherMap.get(n2);
            return node1 == node2;
        }
        return false;
    }
}
